package com.shellSort;

import com.Sort;

/**
 * 我自己对希尔排序的理解
 *
 * @author 罗俊华
 * @date 2021/5/11 - 8:35 上午
 */
public class ShellSortEnhanceByMySelf<Item extends Comparable<Item>> extends Sort<Item> {

    @Override
    public void sort(Item[] comparableArray) {
        int step = 1;
        int N = comparableArray.length;
        while (step < N / 3) {
            step = 3 * step + 1;
        }
        while (step >= 1) {

            for (int sortedTailIndex = step; sortedTailIndex < N; sortedTailIndex++) {
// 在子数组中将每个元素交换到比它大的元素前面去（将比它大的元素都向右移动一格）
                for (int moveIndex = sortedTailIndex; moveIndex >= step && super.less(comparableArray[moveIndex], comparableArray[moveIndex - step]); moveIndex -= step) {

                    super.exchange(comparableArray, moveIndex, moveIndex - step);

                }

            }
            step /= 3;
        }
    }
}
